package 链表系列;
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
//class ListNode {
//    int val;
//    ListNode next;
//    ListNode() {}
//    ListNode(int val) { this.val = val; }
//    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
//}
class Solution {
    /**
     * 自己写的代码
     * 不添加虚节点方式
     * 时间复杂度 O(n)
     * 空间复杂度 O(1)
     * @param head
     * @param val
     * @return
     */
    public ListNode removeElements(ListNode head, int val) {
        while(head!=null && head.val == val){
            head = head.next;   //头指针指向第一个不为val的节点
        }
        if(head==null)  return head;
        ListNode Pnode = head;       //当前节点的上一个节点
        ListNode Lnode = head.next;  //当前节点
        while(Lnode!=null){
            if(Lnode.val == val ){  //如果相等
                Pnode.next = Lnode.next;    //则当前节点的上一个节点的next指针指向当前节点的下一个节点
            }else{
                Pnode = Lnode;      //如果不相等则令上一个节点等于当前节点
            }
            Lnode = Lnode.next;     //当前节点指向下一个节点
        }
        return head;                //返回头指针
    }
    /**
     * 自己写的代码
     * 添加虚节点方式
     * 时间复杂度 O(n)
     * 空间复杂度 O(1)
     * @param head
     * @param val
     * @return
     */
//    public ListNode removeElements(ListNode head, int val) {
//
//        if(head==null)  return head;
//        ListNode dummy = new ListNode(-1,head); //dummy节点为虚拟头节点，它的next指针指向head节点
//        ListNode Pnode = dummy;       //当前节点的上一个节点
//        ListNode Lnode = head;  //当前节点
//        while(Lnode!=null){
//            if(Lnode.val == val ){  //如果相等
//                Pnode.next = Lnode.next;    //则当前节点的上一个节点的next指针指向当前节点的下一个节点
//            }else{
//                Pnode = Lnode;      //如果不相等则令上一个节点等于当前节点
//            }
//            Lnode = Lnode.next;     //当前节点指向下一个节点
//        }
//        return dummy.next;          //这里要注意！！！返回虚拟头节点的指针而不是实际头节点，原因在于虚拟头节点为当前链表的头节点（即防止若head.val == val，head节点并未删除）
//    }
}